{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cousins in Binary Tree II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: replaceValueInTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的堂兄弟节点 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根&nbsp;<code>root</code>&nbsp;，请你将每个节点的值替换成该节点的所有 <strong>堂兄弟节点值的和&nbsp;</strong>。</p>\n",
    "\n",
    "<p>如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 <strong>堂兄弟</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回修改值之后，树的根<em>&nbsp;</em><code>root</code><em>&nbsp;</em>。</p>\n",
    "\n",
    "<p><strong>注意</strong>，一个节点的深度指的是从树根节点到这个节点经过的边数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/11/example11.png\" style=\"width: 571px; height: 151px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [5,4,9,1,10,null,7]\n",
    "<b>输出：</b>[0,0,0,7,7,null,11]\n",
    "<b>解释：</b>上图展示了初始的二叉树和修改每个节点的值之后的二叉树。\n",
    "- 值为 5 的节点没有堂兄弟，所以值修改为 0 。\n",
    "- 值为 4 的节点没有堂兄弟，所以值修改为 0 。\n",
    "- 值为 9 的节点没有堂兄弟，所以值修改为 0 。\n",
    "- 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。\n",
    "- 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。\n",
    "- 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/11/diagram33.png\" style=\"width: 481px; height: 91px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [3,1,2]\n",
    "<b>输出：</b>[0,0,0]\n",
    "<b>解释：</b>上图展示了初始的二叉树和修改每个节点的值之后的二叉树。\n",
    "- 值为 3 的节点没有堂兄弟，所以值修改为 0 。\n",
    "- 值为 1 的节点没有堂兄弟，所以值修改为 0 。\n",
    "- 值为 2 的节点没有堂兄弟，所以值修改为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目的范围是&nbsp;<code>[1, 10<sup>5</sup>]</code> 。</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cousins-in-binary-tree-ii](https://leetcode.cn/problems/cousins-in-binary-tree-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cousins-in-binary-tree-ii](https://leetcode.cn/problems/cousins-in-binary-tree-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,9,1,10,null,7]', '[3,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            nxt = []\n",
    "            nextLevelSum = 0\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    nextLevelSum += node.left.val\n",
    "                if node.right:\n",
    "                    nextLevelSum += node.right.val\n",
    "            \n",
    "            for node in q:\n",
    "                childrenSum = 0\n",
    "                if node.left:\n",
    "                    childrenSum += node.left.val\n",
    "                if node.right:\n",
    "                    childrenSum += node.right.val\n",
    "                child_val = nextLevelSum - childrenSum\n",
    "                if node.left:\n",
    "                    node.left.val = child_val\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val = child_val\n",
    "                    nxt.append(node.right)\n",
    "            q = nxt\n",
    "        root.val = 0\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val, q = 0, [root]\n",
    "        while q:\n",
    "            s, nq = 0, deque()\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    s += node.left.val\n",
    "                    nq.append(node.left)\n",
    "                if node.right:\n",
    "                    s += node.right.val\n",
    "                    nq.append(node.right)\n",
    "            for node in q:\n",
    "                if node.left and node.right:\n",
    "                    node.left.val = node.right.val = s - node.left.val - node.right.val\n",
    "                elif node.left or node.right:\n",
    "                    sub = node.left or node.right\n",
    "                    sub.val = s - sub.val\n",
    "            q = nq\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # bfs\n",
    "        # 结构 [(左节点， 右节点), (左节点， 右节点)……]，表示同一个父节点下的\n",
    "        q = [(root, None)]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            total = 0\n",
    "            for l, r in tmp:\n",
    "                if l: \n",
    "                    total += l.val\n",
    "                    q.append((l.left, l.right))\n",
    "                if r: \n",
    "                    total += r.val\n",
    "                    q.append((r.left, r.right))\n",
    "            \n",
    "            for l, r in tmp:\n",
    "                cnt = total\n",
    "                if l:\n",
    "                    cnt -= l.val\n",
    "                if r:\n",
    "                    cnt -= r.val\n",
    "                if l:\n",
    "                    l.val = cnt\n",
    "                if r:\n",
    "                    r.val = cnt\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        levels = deque([root])\n",
    "        while levels:\n",
    "            if len(levels) <= 2:\n",
    "                for level in levels:\n",
    "                    if level:\n",
    "                        level.val = 0\n",
    "            else:\n",
    "                total = 0\n",
    "                for level in levels:\n",
    "                    if level:\n",
    "                        total += level.val\n",
    "                for i in range(len(levels) // 2):\n",
    "                    rest = total\n",
    "                    if levels[i * 2]:\n",
    "                        rest = rest - levels[i * 2].val\n",
    "                    if levels[i * 2 + 1]:\n",
    "                        rest = rest - levels[i * 2 + 1].val\n",
    "                    if levels[i * 2]:\n",
    "                        levels[i * 2].val = rest\n",
    "                    if levels[i * 2 + 1]:\n",
    "                        levels[i * 2 + 1].val = rest\n",
    "            for _ in range(len(levels)):\n",
    "                node = levels.popleft()\n",
    "                if node:\n",
    "                    if node.left:\n",
    "                        levels.append(node.left)\n",
    "                    else:\n",
    "                        levels.append(None)\n",
    "                    if node.right:\n",
    "                        levels.append(node.right)\n",
    "                    else:\n",
    "                        levels.append(None)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        cur = [root]\n",
    "        while cur:\n",
    "            ne = []\n",
    "            neSum = 0\n",
    "            for node in cur:\n",
    "                if node.left:\n",
    "                    ne.append(node.left)\n",
    "                    neSum += node.left.val\n",
    "                if node.right:\n",
    "                    ne.append(node.right)\n",
    "                    neSum += node.right.val\n",
    "            for node in cur:\n",
    "                childSum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val = neSum - childSum\n",
    "                if node.right:\n",
    "                    node.right.val = neSum - childSum\n",
    "            cur = ne\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "       q = [root]\n",
    "       root.val = 0\n",
    "       while q:\n",
    "          size = len(q)\n",
    "          s = 0\n",
    "          for i in range(size):\n",
    "             x = q[i]\n",
    "             if x.left:\n",
    "                s += x.left.val\n",
    "             if x.right:\n",
    "                s += x.right.val\n",
    "          for _ in range(size):\n",
    "             x = q.pop(0)\n",
    "             cur = 0\n",
    "             if x.left:\n",
    "                cur += x.left.val\n",
    "             if x.right:\n",
    "                cur += x.right.val\n",
    "             if x.left:\n",
    "                x.left.val = s - cur\n",
    "                q.append(x.left)\n",
    "             if x.right:\n",
    "                x.right.val = s - cur\n",
    "                q.append(x.right)\n",
    "       return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cur = [(root, root.val)]\n",
    "        while cur:\n",
    "            levelSum = sum(node.val for node, _ in cur)\n",
    "            ne = []\n",
    "            for node, val in cur:\n",
    "                node.val = levelSum - val\n",
    "                if node.left and node.right:\n",
    "                    ne.append((node.left, node.left.val + node.right.val))\n",
    "                    ne.append((node.right, node.left.val + node.right.val))\n",
    "                elif node.left:\n",
    "                    ne.append((node.left, node.left.val))\n",
    "                elif node.right:\n",
    "                    ne.append((node.right, node.right.val))\n",
    "            cur = ne\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [root]\n",
    "        root.val = 0\n",
    "        while q:\n",
    "            t = q\n",
    "            q = []\n",
    "            next_sum = 0\n",
    "            for item in t:\n",
    "                if item.left:\n",
    "                    q.append(item.left)\n",
    "                    next_sum += item.left.val\n",
    "                if item.right:\n",
    "                    q.append(item.right)\n",
    "                    next_sum += item.right.val\n",
    "            for item in t:\n",
    "                a = 0\n",
    "                if item.left:\n",
    "                    a += item.left.val\n",
    "                if item.right:\n",
    "                    a += item.right.val\n",
    "                if item.left:\n",
    "                    item.left.val = next_sum - a\n",
    "                if item.right:\n",
    "                    item.right.val = next_sum - a\n",
    "            \n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            tmp = queue\n",
    "            queue = []\n",
    "            nxtLevel = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    nxtLevel += node.left.val\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    nxtLevel += node.right.val\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            for node in tmp:\n",
    "                childrenSum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val = nxtLevel - childrenSum\n",
    "                \n",
    "                if node.right:\n",
    "                    node.right.val = nxtLevel - childrenSum\n",
    "        \n",
    "        root.val = 0\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue=[[root.val,root]]\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            sum_val=sum([q.val for i,q in queue])\n",
    "            for del_var,q in queue:\n",
    "                if q.left and q.right:\n",
    "                    temp.append([q.left.val+q.right.val,q.left])\n",
    "                    temp.append([q.left.val+q.right.val,q.right])\n",
    "                elif q.left:\n",
    "                    temp.append([q.left.val,q.left])\n",
    "                elif q.right:\n",
    "                    temp.append([q.right.val,q.right])\n",
    "                #temp_var.append(sum([q.val for j,q in queue if j!=i]))\n",
    "                q.val=sum_val-del_var\n",
    "            queue=temp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q, s = deque([root]), -root.val\n",
    "        while q:\n",
    "            ns = 0\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                node.val += s\n",
    "                x = (node.left and node.left.val or 0) + (node.right and node.right.val or 0)\n",
    "                if node.left:\n",
    "                    ns += node.left.val\n",
    "                    node.left.val = -x\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    ns += node.right.val\n",
    "                    node.right.val = -x\n",
    "                    q.append(node.right)\n",
    "            s = ns\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val=0\n",
    "        q=[root]\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            next_level_sum=0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum+=node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum+=node.right.val\n",
    "            for node in tmp:\n",
    "                children_sum=(node.left.val if node.left else 0)+(node.right.val if node.right else 0)\n",
    "                if node.left:node.left.val=next_level_sum-children_sum\n",
    "                if node.right:node.right.val=next_level_sum-children_sum\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            nei = dict()\n",
    "            level = []\n",
    "            count = 0\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    level.append(node.left)\n",
    "                    count += node.left.val\n",
    "                    nei[node.left] = node.right.val if node.right else 0 \n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    level.append(node.right)\n",
    "                    count += node.right.val\n",
    "                    nei[node.right] = node.left.val if node.left else 0\n",
    "                    queue.append(node.right)\n",
    "            for i in level:\n",
    "                if i in nei:\n",
    "                    i.val = count - nei[i] - i.val\n",
    "                else:\n",
    "                    i.val = 0\n",
    "        root.val = 0\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # BFS\n",
    "        stack = [root]\n",
    "        root.val = 0\n",
    "\n",
    "        while stack:\n",
    "            tmp = stack\n",
    "            stack = []\n",
    "            nextLayerSum = 0\n",
    "\n",
    "            # 第一次遍历，计算下一层所有节点的总和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    nextLayerSum += node.left.val\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    nextLayerSum += node.right.val\n",
    "                    stack.append(node.right)\n",
    "            \n",
    "            # 第二次遍历，更新每个子节点的值\n",
    "            for node in tmp:\n",
    "                childrenSum = 0\n",
    "                if node.left:  childrenSum += node.left.val\n",
    "                if node.right: childrenSum += node.right.val\n",
    "                if node.left: node.left.val = nextLayerSum - childrenSum\n",
    "                if node.right: node.right.val = nextLayerSum - childrenSum\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cur_level = [(root, None)]\n",
    "        next_level = []\n",
    "        while cur_level:\n",
    "\n",
    "            ssum = sum(x.val for x, _ in cur_level)\n",
    "            val_list = [0] * len(cur_level)\n",
    "\n",
    "            for i, (cur, parent) in enumerate(cur_level):\n",
    "\n",
    "                cur_sum = ssum - cur.val\n",
    "\n",
    "                if i - 1 >= 0 and cur_level[i - 1][1] is parent:\n",
    "                    cur_sum -= cur_level[i - 1][0].val\n",
    "                if i + 1 < len(cur_level) and cur_level[i + 1][1] is parent:\n",
    "                    cur_sum -= cur_level[i + 1][0].val\n",
    "\n",
    "                val_list[i] = cur_sum\n",
    "\n",
    "                if cur.left:\n",
    "                    next_level.append((cur.left, cur))\n",
    "                if cur.right:\n",
    "                    next_level.append((cur.right, cur))\n",
    "\n",
    "            for x, (node, _) in zip(val_list, cur_level):\n",
    "                node.val = x\n",
    "            cur_level = next_level\n",
    "            next_level = []\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val=0\n",
    "        q=[root]\n",
    "        while q:\n",
    "            temp=q\n",
    "            q=[]\n",
    "            nxt_sum=0\n",
    "            for node in temp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    nxt_sum+=node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    nxt_sum+=node.right.val\n",
    "            for node in temp:\n",
    "                child_sum=(node.left.val if node.left else 0)+(node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val=nxt_sum-child_sum\n",
    "                if node.right:\n",
    "                    node.right.val=nxt_sum-child_sum\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue=[[root.val,root]]\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            sum_val=sum([q.val for i,q in queue])\n",
    "            for del_var,q in queue:\n",
    "                if q.left and q.right:\n",
    "                    temp.append([q.left.val+q.right.val,q.left])\n",
    "                    temp.append([q.left.val+q.right.val,q.right])\n",
    "                elif q.left:\n",
    "                    temp.append([q.left.val,q.left])\n",
    "                elif q.right:\n",
    "                    temp.append([q.right.val,q.right])\n",
    "                #temp_var.append(sum([q.val for j,q in queue if j!=i]))\n",
    "                q.val=sum_val-del_var\n",
    "            queue=temp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            \n",
    "            next_sum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_sum += node.right.val\n",
    "            \n",
    "            for node in tmp:\n",
    "                child_sum = (\n",
    "                    (node.left.val if node.left else 0) +\n",
    "                    (node.right.val if node.right else 0)\n",
    "                )\n",
    "                if node.left:\n",
    "                    node.left.val = next_sum - child_sum\n",
    "                if node.right:\n",
    "                    node.right.val = next_sum - child_sum\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue=[[root.val,root]]\n",
    "        sum_val=root.val\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            sum_val_temp=0\n",
    "            for del_var,q in queue:\n",
    "                if q.left and q.right:\n",
    "                    temp.append([q.left.val+q.right.val,q.left])\n",
    "                    temp.append([q.left.val+q.right.val,q.right])\n",
    "                    sum_val_temp+=q.left.val\n",
    "                    sum_val_temp+=q.right.val\n",
    "                elif q.left:\n",
    "                    temp.append([q.left.val,q.left])\n",
    "                    sum_val_temp+=q.left.val\n",
    "                elif q.right:\n",
    "                    temp.append([q.right.val,q.right])\n",
    "                    sum_val_temp+=q.right.val\n",
    "                #temp_var.append(sum([q.val for j,q in queue if j!=i]))\n",
    "                q.val=sum_val-del_var\n",
    "            sum_val=sum_val_temp\n",
    "            queue=temp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def replaceValueInTree(self, root):\n",
    "        \"\"\"\n",
    "        作者：_G_\n",
    "        链接：https://leetcode.cn/problems/cousins-in-binary-tree-ii/solutions/2233195/bfsyi-ci-bian-li-pythonjin-shuang-bai-26-xxda/\n",
    "        来源：力扣（LeetCode）\n",
    "        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        :param root:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        lstn, sumv, root.val = [root], root.val, - root.val\n",
    "        while lstn:\n",
    "            lstn_, sumv_ = [], 0\n",
    "            for node in lstn:\n",
    "                node.val += sumv\n",
    "                tmp = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                sumv_ += tmp\n",
    "                if node.left :\n",
    "                    node.left.val  = - tmp\n",
    "                    lstn_.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val = - tmp\n",
    "                    lstn_.append(node.right)\n",
    "            lstn, sumv = lstn_, sumv_\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0  # 初始化根节点的堂兄弟结点和0\n",
    "        queue = deque([root, ])  \n",
    "        while queue:\n",
    "            tem = list(queue)  # 创建队列的临时副本，以防队列在遍历时被修改\n",
    "\n",
    "            next_level_sum = 0  # 当前遍历层的下一层的节点值之和\n",
    "\n",
    "            # 遍历当前层的每个结点，通过每个结点的左右儿子，计算下一层的结点值之和next_level_sum\n",
    "            for node in tem:\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 然后再次遍历当前层的每个结点x，计算x的左右孩子结点值之和childrenSum,更新x左右儿子结点值为nextLevelSum-childrenSum\n",
    "            for node in tem:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "\n",
    "                # 对于一个结点x来说,它的所有堂兄弟结点值的和 = 这一层结点之和减去x及其兄弟结点的值之和\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "\n",
    "                # 遍历结束后，同时要更新队列，使队列的起始结点为下一层节点\n",
    "                queue.popleft()\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def replaceValueInTree(self, root):\n",
    "        lstn, sumv, root.val = [root], root.val, - root.val\n",
    "        while lstn:\n",
    "            lstn_, sumv_ = [], 0\n",
    "            for node in lstn:\n",
    "                node.val += sumv\n",
    "                tmp = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                sumv_ += tmp\n",
    "                if node.left : \n",
    "                    node.left.val  = - tmp\n",
    "                    lstn_.append(node.left)\n",
    "                if node.right: \n",
    "                    node.right.val = - tmp\n",
    "                    lstn_.append(node.right)\n",
    "            lstn, sumv = lstn_, sumv_        \n",
    "        return root   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            sum_ = 0\n",
    "            for a in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "                sum_ += node.left.val if node.left else 0\n",
    "                sum_ += node.right.val if node.right else 0\n",
    "                if level < 2:\n",
    "                    node.val = 0\n",
    "                    continue\n",
    "            level += 1\n",
    "            for index in range(0, len(queue), 2):\n",
    "                s = (queue[index].val if queue[index] else 0) + (queue[index + 1].val if queue[index + 1] else 0)\n",
    "                if queue[index]:\n",
    "                    queue[index].val = sum_ - s\n",
    "                if queue[index + 1]:\n",
    "                    queue[index + 1].val = sum_ - s\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            next_level_sum = 0\n",
    "            for node in temp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "            for node in temp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val = next_level_sum - children_sum\n",
    "                if node.right:\n",
    "                    node.right.val =next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "            \n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            total=0\n",
    "            for cur in q:\n",
    "                if cur.left:\n",
    "                    total+=cur.left.val\n",
    "                if cur.right:\n",
    "                    total+=cur.right.val\n",
    "            for _ in range(size):\n",
    "                cur=q.popleft()\n",
    "                child_sum=(cur.left.val if cur.left else 0) +(cur.right.val if cur.right else 0)\n",
    "                if cur.left:\n",
    "                    cur.left.val=total-child_sum\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    cur.right.val=total-child_sum\n",
    "                    q.append(cur.right)\n",
    "        root.val=0\n",
    "        return root\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            nxtsum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    nxtsum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    nxtsum += node.right.val\n",
    "\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = nxtsum - children_sum\n",
    "                if node.right: node.right.val = nxtsum - children_sum\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            for a in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "                if level < 2:\n",
    "                    node.val = 0\n",
    "                    continue\n",
    "            level += 1\n",
    "            sum_ = sum(map(lambda x: x.val if x else 0, queue))\n",
    "            for index in range(0, len(queue), 2):\n",
    "                s = (queue[index].val if queue[index] else 0) + (queue[index + 1].val if queue[index + 1] else 0)\n",
    "                if queue[index]:\n",
    "                    queue[index].val = sum_ - s\n",
    "                if queue[index + 1]:\n",
    "                    queue[index + 1].val = sum_ - s\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q=[root]\n",
    "        while q:\n",
    "            t=q;q=[];d=[];he =0\n",
    "            for n in t:\n",
    "                a=b=g=0\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                    a=n.left.val;g+=1\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "                    b=n.right.val;g+=1\n",
    "                x=a+b \n",
    "                d+=[x]*g\n",
    "                he+=x \n",
    "            for n,v in zip(q,d):\n",
    "                n.val=he-v\n",
    "        root.val=0\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if(not root):\n",
    "            return None\n",
    "        root.val = 0\n",
    "        level= [root]\n",
    "        while(len(level) > 0):\n",
    "            levelSum = 0\n",
    "            tmp = []\n",
    "            for node in level:\n",
    "                if(node.left):\n",
    "                    levelSum += node.left.val\n",
    "                if(node.right):\n",
    "                    levelSum += node.right.val \n",
    "            for node in level:\n",
    "                levelChildren = 0\n",
    "                if(node.left):\n",
    "                    levelChildren += node.left.val\n",
    "                if(node.right):\n",
    "                    levelChildren += node.right.val \n",
    "                if(node.left):\n",
    "                    node.left.val = levelSum - levelChildren\n",
    "                    tmp.append(node.left)\n",
    "                if(node.right):\n",
    "                    node.right.val = levelSum - levelChildren\n",
    "                    tmp.append(node.right)\n",
    "            level = tmp[:]\n",
    "        return root\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q=[root]\n",
    "        while q:\n",
    "            t=q;q=[];d=[];he =0\n",
    "            for n in t:\n",
    "                a=b=g=0\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                    a=n.left.val;g+=1\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "                    b=n.right.val;g+=1\n",
    "                x=a+b \n",
    "                d+=[x]*g\n",
    "                he+=x \n",
    "            for n,v in zip(q,d):\n",
    "                n.val=he-v\n",
    "        root.val=0\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val=0\n",
    "        q=[root]\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            next_level_sum=0                #下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum+=node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum+=node.right.val\n",
    "            \n",
    "            for node in tmp:               #再次遍历，更新下一层的节点值\n",
    "                children_sum=(node.left.val if node.left else 0)+(node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val=next_level_sum-children_sum\n",
    "                if node.right:\n",
    "                    node.right.val=next_level_sum-children_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 再次遍历，更新下一层的节点值\n",
    "            for node in tmp:\n",
    "                children_sum = (node.left.val if node.left else 0) + \\\n",
    "                               (node.right.val if node.right else 0)\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        s = 0\n",
    "        if root.left:\n",
    "            s += root.left.val\n",
    "        if root.right:\n",
    "            s += root.right.val\n",
    "        q = collections.deque([(root.left, root.right)])\n",
    "        while s:\n",
    "            new_s = 0\n",
    "            for _ in range(len(q)):\n",
    "                l, r = q.popleft()\n",
    "                tmp = (l.val if l else 0) + (r.val if r else 0)\n",
    "                if l:\n",
    "                    l.val = s - tmp\n",
    "                    q.append((l.left, l.right))\n",
    "                    new_s += l.left.val if l.left else 0\n",
    "                    new_s += l.right.val if l.right else 0\n",
    "                if r:\n",
    "                    r.val = s - tmp\n",
    "                    q.append((r.left, r.right))\n",
    "                    new_s += r.left.val if r.left else 0\n",
    "                    new_s += r.right.val if r.right else 0\n",
    "            s = new_s\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque([[root, -1]])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            counts = {}\n",
    "            sums = 0\n",
    "            for i in range(n):\n",
    "                node, parent = queue[i]\n",
    "                sums += node.val\n",
    "                counts[parent] = counts.get(parent, 0) + node.val\n",
    "            for _ in range(n):\n",
    "                node, parent = queue.popleft()\n",
    "                node.val = sums - counts[parent]\n",
    "                if node.left:\n",
    "                    queue.append([node.left, node])\n",
    "                if node.right:\n",
    "                    queue.append([node.right, node])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = [(root,root)]\n",
    "        while q:\n",
    "            num = len(q)\n",
    "            cur_sum_dict = collections.defaultdict(int)\n",
    "            for i in range(num):\n",
    "                cur,par = q[i]\n",
    "                cur_sum_dict[par] += cur.val\n",
    "                if cur.left: q.append((cur.left,cur))\n",
    "                if cur.right: q.append((cur.right,cur))\n",
    "            cur_sum = sum(cur_sum_dict.values())\n",
    "            for i in range(num):\n",
    "                cur,par = q.pop(0)\n",
    "                cur.val = cur_sum - cur_sum_dict[par]\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            next_sum_node = 0\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    next_sum_node += node.left.val\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    next_sum_node +=node.right.val\n",
    "                    q.append(node.right)\n",
    "\n",
    "            for node in tmp:\n",
    "                borther_node_sum = (node.right.val if node.right else 0) + (node.left.val if node.left else 0)\n",
    "                print(borther_node_sum)\n",
    "                if node.left:\n",
    "                    node.left.val  = next_sum_node -borther_node_sum\n",
    "                if node.right:\n",
    "                    node.right.val  = next_sum_node -borther_node_sum\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = deque([root])\n",
    "        root.val = 0\n",
    "        while q:\n",
    "            sum_val = 0\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    sum_val += node.left.val\n",
    "                if node.right:\n",
    "                    sum_val += node.right.val\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                child_val = 0\n",
    "                if node.left:\n",
    "                    child_val += node.left.val\n",
    "                if node.right:\n",
    "                    child_val += node.right.val\n",
    "                if node.left:\n",
    "                    node.left.val = sum_val - child_val\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val = sum_val - child_val\n",
    "                    q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 层序遍历\n",
    "        dummy_node = TreeNode(left = root)\n",
    "        q = deque([(root, dummy_node)])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            s = sum(x[0].val for x in q)\n",
    "            tmp = [0] * n\n",
    "            for i in range(n):\n",
    "                tmp[i] = s - q[i][0].val\n",
    "                if i - 1 >= 0 and q[i - 1][1] == q[i][1]:\n",
    "                    tmp[i] -= q[i - 1][0].val\n",
    "                if i + 1 < n and q[i + 1][1] == q[i][1]:\n",
    "                    tmp[i] -= q[i + 1][0].val\n",
    "            for i in range(n):\n",
    "                q[i][0].val = tmp[i]\n",
    "            for i in range(n):\n",
    "                c, f = q.popleft()\n",
    "                if c.left:\n",
    "                    q.append((c.left, c))\n",
    "                if c.right:\n",
    "                    q.append((c.right, c))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val=0;q=[root]\n",
    "        while q:\n",
    "            #层序遍历\n",
    "            t=q;q=[];d=[]\n",
    "            he =0#本层的累加和\n",
    "            for n in t:\n",
    "                a=b=g=0\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                    a=n.left.val;g+=1\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "                    b=n.right.val;g+=1\n",
    "                #左右孩子的和\n",
    "                x=a+b\n",
    "                #g记录了有几个孩子，d和q长度一致\n",
    "                d += [x]*g\n",
    "                he += x \n",
    "            for n,v in zip(q,d):\n",
    "                n.val=he-v\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree_mine(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "        level_map = {}\n",
    "        level = 1\n",
    "        queue = [root]\n",
    "        m = {}  # 存储当前节点的父节点\n",
    "        nodemap = {}\n",
    "        levelsum = {}\n",
    "        while queue:\n",
    "            stack = []\n",
    "            while queue:\n",
    "                stack.append(queue.pop(0))\n",
    "            current_level_sum = 0\n",
    "            while stack:\n",
    "                node = stack.pop(0)\n",
    "                current_level_sum += node.val\n",
    "                if level not in level_map.keys():\n",
    "                    level_map[level] = []\n",
    "                level_map[level].append(node)\n",
    "                if node.left is not None:\n",
    "                    queue.append(node.left)\n",
    "                    m[node.left] = node\n",
    "                    nodemap[node.left] = node.left.val\n",
    "                if node.right is not None:\n",
    "                    queue.append(node.right)\n",
    "                    m[node.right] = node\n",
    "                    nodemap[node.right] = node.right.val\n",
    "            # 更新当前层的元素值总和\n",
    "            levelsum[level] = current_level_sum\n",
    "            level += 1\n",
    "        # 处理层次数据\n",
    "        for index, nodes in level_map.items():\n",
    "            if index == 1 or index == 2:\n",
    "                for node in nodes:\n",
    "                    node.val = 0\n",
    "            else:\n",
    "                for node in nodes:\n",
    "                    brothers = [nodemap[other] for other in nodes if other == node or m[other] == m[node]]\n",
    "                    # print(\"nodes=\", nodes, \"others=\", others, \"node=\", node, \"m[node]=\", m[node])\n",
    "                    if len(brothers) > 0:\n",
    "                        node.val = levelsum[index] - sum(brothers)\n",
    "                    else:\n",
    "                        node.val = levelsum[index] - node.val\n",
    "\n",
    "        return root\n",
    "\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            # 两个节点深度相同，但是他们的父节点不同，那就是堂兄弟，将该节点值换为所有堂兄弟之和\n",
    "            Q = [(root, 0)]\n",
    "            while Q:\n",
    "                dic = defaultdict(list)\n",
    "                sum_ = 0\n",
    "                for _ in range(len(Q)):\n",
    "                    node, father = Q.pop(0)\n",
    "                    dic[father].append(node)\n",
    "                    sum_ += node.val\n",
    "                    if node.left:\n",
    "                        Q.append((node.left, node))\n",
    "                    if node.right:\n",
    "                        Q.append((node.right, node))\n",
    "                # print(sum_,dic)\n",
    "                for k, v in dic.items():\n",
    "                    tmp = 0\n",
    "                    for n in v:\n",
    "                        tmp += n.val\n",
    "                    for n in v:\n",
    "                        n.val = sum_ - tmp\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        queue = deque([root, ])\n",
    "        while queue:\n",
    "            tem = list(queue)\n",
    "            next_level_sum = 0  # 下一层的节点值之和\n",
    "\n",
    "            # 遍历当前层的每个结点，通过每个结点的左右儿子，计算下一层的结点值之和next_level_sum\n",
    "            for node in tem:\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    next_level_sum += node.left.val\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    next_level_sum += node.right.val\n",
    "\n",
    "            # 然后再次遍历当前层的每个结点x，计算x的左右孩子结点值之和childrenSum,更新x左右儿子结点值为nextLevelSum-childrenSum\n",
    "            for node in tem:\n",
    "                children_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "\n",
    "                # 对于一个结点x来说,它的所有堂兄弟结点值的和 = 这一层结点之和减去x及其兄弟结点的值之和\n",
    "                if node.left: node.left.val = next_level_sum - children_sum\n",
    "                if node.right: node.right.val = next_level_sum - children_sum\n",
    "                queue.popleft()\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "\n",
    "\n",
    "        q =deque([root])\n",
    "        c=0\n",
    "        \n",
    "\n",
    "        while q:\n",
    "            c+=1\n",
    "            n=len(q)\n",
    "            d=[]\n",
    "            he =0\n",
    "            for i in range(n):\n",
    "                node = q.popleft()\n",
    "                a=b=0\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    a=node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    b=node.right.val\n",
    "                x=a+b \n",
    "                d.append((node,x))\n",
    "                he+=x \n",
    "            if c>=2:\n",
    "                for k,v in d:\n",
    "                    w=he -v \n",
    "                    if k.left:\n",
    "                        k.left.val=w \n",
    "                    if k.right:\n",
    "                        k.right.val=w\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        root.val=0\n",
    "        if root.left:\n",
    "            root.left.val=0\n",
    "        if root.right:\n",
    "            root.right.val=0\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        dummy = TreeNode()\n",
    "        dummy.left = root\n",
    "        queue = collections.deque()\n",
    "        queue.append([root, dummy])\n",
    "        while queue:\n",
    "            layerSum = 0\n",
    "            fatherNodes = []\n",
    "            for _ in range(len(queue)):\n",
    "                curNode, fatherNode = queue.popleft()\n",
    "                layerSum += curNode.val\n",
    "                if not fatherNodes:\n",
    "                    fatherNodes.append(fatherNode)\n",
    "                elif fatherNode != fatherNodes[-1]:\n",
    "                    fatherNodes.append(fatherNode)\n",
    "                if curNode.left:\n",
    "                    queue.append([curNode.left, curNode])\n",
    "                if curNode.right:\n",
    "                    queue.append([curNode.right, curNode])\n",
    "            for fatherNode in fatherNodes:\n",
    "                sonSum = 0\n",
    "                # if fatherNode.left:\n",
    "                #     sonSum += fatherNode.left.val\n",
    "                # if fatherNode.right:\n",
    "                #     sonSum += fatherNode.right.val\n",
    "                sonSum += fatherNode.left.val if fatherNode.left else 0\n",
    "                sonSum += fatherNode.right.val if fatherNode.right else 0\n",
    "                if fatherNode.left:\n",
    "                    fatherNode.left.val = layerSum - sonSum\n",
    "                if fatherNode.right:\n",
    "                    fatherNode.right.val = layerSum - sonSum\n",
    "        return root\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        res= []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            new_q = []\n",
    "            s = 0\n",
    "            for node in q:\n",
    "                s += node.val\n",
    "                if node.left: new_q.append(node.left)\n",
    "                if node.right: new_q.append(node.right)\n",
    "            res.append(s)\n",
    "            q = new_q\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        n = len(res)\n",
    "        for s in res[1:]:\n",
    "            new_q = []\n",
    "            for node in q:\n",
    "                t = s - (node.left.val if node.left else 0) - (node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val = t\n",
    "                    new_q.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val = t\n",
    "                    new_q.append(node.right)\n",
    "            q = new_q\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        s = [0] * (10 ** 5 + 1)\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        i = 0\n",
    "        while q:\n",
    "            tq = q\n",
    "            q = []\n",
    "            for node in tq:\n",
    "                s[i] += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            i += 1\n",
    "        \n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        root.val = 0\n",
    "        i = 0\n",
    "        while q:\n",
    "            tq = q\n",
    "            q = []\n",
    "            for node in tq:\n",
    "                cur = 0\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    cur += node.left.val\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    cur += node.right.val\n",
    "                if node.left:\n",
    "                    node.left.val = s[i + 1] - cur\n",
    "                if node.right:\n",
    "                    node.right.val = s[i + 1] - cur\n",
    "            i += 1\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = deque()\n",
    "        if not root:\n",
    "            return None\n",
    "        levelSum = []\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            tmp = []\n",
    "            t = len(q)\n",
    "            for i in range(t):\n",
    "                cur = q.popleft()\n",
    "                if cur.left != None:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right != None:\n",
    "                    q.append(cur.right)\n",
    "                tmp.append(cur.val)\n",
    "            levelSum.append(sum(tmp))\n",
    "        q.append(root)\n",
    "        root.val -=levelSum[0]\n",
    "        level = 1\n",
    "        while q and level < len(levelSum):\n",
    "            t = len(q)\n",
    "            for i in range(t):\n",
    "                cur = q.popleft()\n",
    "                s = 0\n",
    "                if cur.left !=None:\n",
    "                    q.append(cur.left)\n",
    "                    s +=cur.left.val\n",
    "                if cur.right != None:\n",
    "                    q.append(cur.right)\n",
    "                    s += cur.right.val\n",
    "                if cur.left !=None:\n",
    "                    cur.left.val = levelSum[level] - s\n",
    "                if cur.right != None:\n",
    "                    cur.right.val = levelSum[level] - s\n",
    "            level +=1\n",
    "        return root\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q = deque([root])\n",
    "        cnt = Counter()  # 存当前节点所有儿子节点的值的和\n",
    "        father = dict()  # 存每个节点的父亲节点\n",
    "        father[root] = 0  # 根节点的父亲节点\n",
    "        cnt[0] = root.val\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            s = sum(node.val for node in tmp)  # 求当前层所有节点的值的和\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    cnt[node] += node.left.val\n",
    "                    father[node.left] = node\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    cnt[node] += node.right.val\n",
    "                    father[node.right] = node\n",
    "                    q.append(node.right)\n",
    "                node.val = s - cnt[father[node]]\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        deep_sum_dict = defaultdict(int)\n",
    "        stack = [(root, 1)]  # 使用栈进行遍历\n",
    "\n",
    "        while stack:\n",
    "            node, deep = stack.pop()\n",
    "            deep_sum_dict[deep] += node.val\n",
    "            if node.left:\n",
    "                stack.append((node.left, deep + 1))\n",
    "            if node.right:\n",
    "                stack.append((node.right, deep + 1))\n",
    "\n",
    "        stack = [(root, 1, root.val)]\n",
    "        while stack:\n",
    "            node, deep, level_sum = stack.pop()\n",
    "            node.val = deep_sum_dict[deep] - level_sum\n",
    "            son_sum = ((node.left.val if node.left else 0) +\n",
    "                       (node.right.val if node.right else 0))\n",
    "            if node.left:\n",
    "                stack.append((node.left, deep + 1, son_sum))\n",
    "            if node.right:\n",
    "                stack.append((node.right, deep + 1, son_sum))\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        cnt=Counter()\n",
    "        floor=0\n",
    "        while q:\n",
    "            temp=0\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                node=q.popleft()\n",
    "                temp+=node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            cnt[floor]=temp\n",
    "            floor+=1\n",
    "        root.val=0\n",
    "        q.append(root)\n",
    "        floor=1\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                node=q.popleft()\n",
    "                temp=0\n",
    "                if node.left:\n",
    "                    temp+=node.left.val\n",
    "                if node.right:\n",
    "                    temp+=node.right.val\n",
    "                if node.left:\n",
    "                    node.left.val=cnt[floor]-temp\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val=cnt[floor]-temp\n",
    "                    q.append(node.right)\n",
    "            floor+=1\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        cnt=Counter()\n",
    "        floor=0\n",
    "        while q:\n",
    "            temp=0\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                node=q.popleft()\n",
    "                temp+=node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            cnt[floor]=temp\n",
    "            floor+=1\n",
    "        root.val=0\n",
    "        q.append(root)\n",
    "        floor=1\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                node=q.popleft()\n",
    "                temp=0\n",
    "                temp = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)\n",
    "                if node.left:\n",
    "                    node.left.val=cnt[floor]-temp\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    node.right.val=cnt[floor]-temp\n",
    "                    q.append(node.right)\n",
    "            floor+=1\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        res = TreeNode(0)\n",
    "        a = []\n",
    "        b = []\n",
    "        if root.left:\n",
    "            a.append(root.left)\n",
    "            res.left = TreeNode(0)\n",
    "            b.append(res.left)\n",
    "        if root.right:\n",
    "            a.append(root.right)\n",
    "            res.right = TreeNode(0)\n",
    "            b.append(res.right)\n",
    "        while a:\n",
    "            total = 0\n",
    "            for node in a:\n",
    "                if node.left:\n",
    "                    total += node.left.val\n",
    "                if node.right:\n",
    "                    total += node.right.val\n",
    "            aa, bb = [], []\n",
    "            for i, node in enumerate(a):\n",
    "                if node.left:\n",
    "                    if node.right:\n",
    "                        aa.append(node.left)\n",
    "                        b[i].left = TreeNode(total - node.left.val - node.right.val)\n",
    "                        bb.append(b[i].left)\n",
    "                        aa.append(node.right)\n",
    "                        b[i].right = TreeNode(total - node.left.val - node.right.val)\n",
    "                        bb.append(b[i].right)\n",
    "                    else:\n",
    "                        aa.append(node.left)\n",
    "                        b[i].left = TreeNode(total - node.left.val)\n",
    "                        bb.append(b[i].left)\n",
    "                else:\n",
    "                    if node.right:\n",
    "                        aa.append(node.right)\n",
    "                        b[i].right = TreeNode(total - node.right.val)\n",
    "                        bb.append(b[i].right)\n",
    "            a, b = aa, bb\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 层序遍历\n",
    "        q = deque()\n",
    "        q.append((root,0,root.val))\n",
    "        hashmap = {}\n",
    "        \n",
    "        while q:\n",
    "            node,depth,sums = q.popleft()\n",
    "            if depth in hashmap:\n",
    "                hashmap[depth].append((node,sums))\n",
    "            else:\n",
    "                hashmap[depth] = [(node,sums)]\n",
    "            s = 0 \n",
    "            if node.left:\n",
    "                s += node.left.val\n",
    "            if node.right:\n",
    "                s += node.right.val\n",
    "\n",
    "            if node.left:\n",
    "                q.append((node.left,depth+1,s))\n",
    "            if node.right:\n",
    "                q.append((node.right,depth+1,s))\n",
    "        \n",
    "        for i in range(len(hashmap)):\n",
    "            a = 0\n",
    "            for node,_ in hashmap[i]:\n",
    "                a += node.val\n",
    "            for node,sums in hashmap[i]:\n",
    "                node.val = a - sums\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cur = [root]\n",
    "        weight = []\n",
    "        \n",
    "        while cur:\n",
    "        \n",
    "            nxt = []\n",
    "            for n in cur:\n",
    "                n.left and nxt.append(n.left)\n",
    "                n.right and nxt.append(n.right)\n",
    "            \n",
    "            cur = nxt\n",
    "            weight.append(sum([n.val for n in cur]))\n",
    "            \n",
    "        print(weight)\n",
    "        \n",
    "        \n",
    "        def dfs(node, lv):\n",
    "            tmp=weight[lv]\n",
    "            if node.left:\n",
    "                tmp -= node.left.val\n",
    "            if node.right:\n",
    "                tmp -= node.right.val\n",
    "            if node.left:\n",
    "                node.left.val = tmp\n",
    "            if node.right:\n",
    "                node.right.val = tmp\n",
    "            node.left and dfs(node.left, lv + 1)\n",
    "            node.right and dfs(node.right,lv + 1)\n",
    "            \n",
    "        \n",
    "        root.val = 0\n",
    "        dfs(root, 0)\n",
    "        \n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        sums_list = []\n",
    "        def dfs(node, depth):\n",
    "            if node is None:\n",
    "                return\n",
    "            if depth > len(sums_list):\n",
    "                sums_list.append(node.val)\n",
    "            else:\n",
    "                sums_list[depth-1] += node.val\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "\n",
    "        dfs(root, 1)\n",
    "\n",
    "        root.val = 0\n",
    "        depth = 0\n",
    "        qu = [root]\n",
    "        while qu:\n",
    "            size = len(qu)\n",
    "            for _ in range(size):\n",
    "                x = qu[0]\n",
    "                cnt = 0\n",
    "                if x.left:\n",
    "                    cnt += x.left.val\n",
    "                    qu.append(x.left)\n",
    "                if x.right:\n",
    "                    cnt += x.right.val\n",
    "                    qu.append(x.right)\n",
    "                if depth < len(sums_list) - 1:\n",
    "                    if x.left:\n",
    "                        x.left.val = sums_list[depth+1] - cnt\n",
    "                    if x.right:\n",
    "                        x.right.val = sums_list[depth+1] - cnt\n",
    "\n",
    "                del qu[0]\n",
    "            depth += 1\n",
    "\n",
    "        return root\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        d = {}\n",
    "        def findb(p):\n",
    "            d[p] = 0\n",
    "            if p.left:\n",
    "                findb(p.left)\n",
    "            if p.right:\n",
    "                findb(p.right)\n",
    "            if p.left and p.right:\n",
    "                d[p.left] = p.right.val\n",
    "                d[p.right] = p.left.val\n",
    "        \n",
    "        findb(root)\n",
    "        root.val = 0\n",
    "        q = [root]\n",
    "        start = 0\n",
    "        while q:\n",
    "            l = []\n",
    "            count = 0\n",
    "            for i in q:\n",
    "                count += i.val\n",
    "                l.append(i)\n",
    "            q = []\n",
    "            # print(count)\n",
    "            for i in l:\n",
    "                i.val = count - d[i] - i.val\n",
    "                if i.left:\n",
    "                    q.append(i.left)\n",
    "                if i.right:\n",
    "                    q.append(i.right)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        sum_d = []\n",
    "\n",
    "        def dfs1(node, d):\n",
    "            while len(sum_d) <= d:\n",
    "                sum_d.append(0)\n",
    "            sum_d[d] += node.val\n",
    "            if node.left is not None:\n",
    "                dfs1(node.left, d + 1)\n",
    "            if node.right is not None:\n",
    "                dfs1(node.right, d + 1)\n",
    "\n",
    "        def dfs2(node, d):\n",
    "            sum_son = 0\n",
    "            if node.left is not None:\n",
    "                sum_son += node.left.val\n",
    "                dfs2(node.left, d + 1)\n",
    "            if node.right is not None:\n",
    "                sum_son += node.right.val\n",
    "                dfs2(node.right, d + 1)\n",
    "            if node.left is not None:\n",
    "                node.left.val = sum_d[d + 1] - sum_son\n",
    "            if node.right is not None:\n",
    "                node.right.val = sum_d[d + 1] - sum_son\n",
    "\n",
    "        dfs1(root, 0)\n",
    "        dfs2(root, 0)\n",
    "        root.val = 0\n",
    "        print(sum_d)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        tot = [0] * (10 ** 5 + 10)\n",
    "        def dfs(u, d):\n",
    "            if u == None: return\n",
    "            tot[d] += u.val\n",
    "            dfs(u.left, d + 1)\n",
    "            dfs(u.right, d + 1)\n",
    "        \n",
    "        def update(u, d):\n",
    "            if u == None: return\n",
    "            ne = 0\n",
    "            \n",
    "            if u.left: ne += u.left.val\n",
    "            if u.right: ne += u.right.val\n",
    "            \n",
    "            update(u.left, d + 1)\n",
    "            update(u.right, d + 1)\n",
    "\n",
    "            k = 0 if ne == tot[d + 1] else tot[d + 1] - ne\n",
    "            \n",
    "            if u.left: u.left.val = k\n",
    "            if u.right: u.right.val = k\n",
    "            \n",
    "\n",
    "        dfs(root, 0)\n",
    "        update(root, 0)\n",
    "        root.val = 0\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        list1=[root]\n",
    "        while list1:\n",
    "            temp_list=[]\n",
    "            for node in list1:\n",
    "                sum1=0\n",
    "                if node.left:\n",
    "                    sum1+=node.left.val\n",
    "                    temp_list.append(node.left)\n",
    "                if node.right:\n",
    "                    sum1+=node.right.val\n",
    "                    temp_list.append(node.right)\n",
    "                node.val=sum1\n",
    "            list1=temp_list.copy()\n",
    "\n",
    "        def myfun1(last_node_list):\n",
    "            if last_node_list==[]:\n",
    "                return\n",
    "            \n",
    "            sum1=0\n",
    "            for node in last_node_list:\n",
    "                sum1+=node.val\n",
    "            temp_list=[]\n",
    "            for node in last_node_list:\n",
    "                if node.left:\n",
    "                    temp_list.append(node.left)\n",
    "                if node.right:\n",
    "                    temp_list.append(node.right)\n",
    "            myfun1(temp_list)\n",
    "\n",
    "            for node in last_node_list:\n",
    "                temp=sum1-node.val\n",
    "                if node.left:\n",
    "                    node.left.val=temp\n",
    "                if node.right:\n",
    "                    node.right.val=temp\n",
    "                \n",
    "        myfun1([root])\n",
    "        root.val=0\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        sum_dep = dict()\n",
    "        def dfs(now, dep):\n",
    "            sum_dep[dep] = sum_dep.get(dep, 0) + now.val\n",
    "            if now.left:\n",
    "                dfs(now.left, dep + 1)\n",
    "            if now.right:\n",
    "                dfs(now.right, dep + 1)\n",
    "        def dfs2(now, dep):\n",
    "            son_total = 0\n",
    "            if now.left:\n",
    "                son_total += now.left.val\n",
    "            if now.right:\n",
    "                son_total += now.right.val\n",
    "            ret = sum_dep.get(dep + 1, 0) - son_total\n",
    "            if now.left:\n",
    "                now.left.val = ret\n",
    "                dfs2(now.left, dep + 1)\n",
    "            if now.right:\n",
    "                now.right.val = ret\n",
    "                dfs2(now.right, dep + 1)\n",
    "        dfs(root, 0)\n",
    "        dfs2(root, 0)\n",
    "        root.val = 0\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        levelSum=[]\n",
    "        dctFa={}\n",
    "        def initDctBFS(root,level,father):\n",
    "            if not root:\n",
    "                return\n",
    "            if len(levelSum)<=level:\n",
    "                levelSum.append(0)\n",
    "            levelSum[level]+=root.val\n",
    "            dctFa.setdefault(father,0)\n",
    "            dctFa[father]+=root.val\n",
    "            initDctBFS(root.left,level+1,root)\n",
    "            initDctBFS(root.right,level+1,root)\n",
    "        def BFS(root,level,father):\n",
    "            if not root:\n",
    "                return\n",
    "            root.val=levelSum[level]-dctFa[father]\n",
    "            BFS(root.left,level+1,root)\n",
    "            BFS(root.right,level+1,root)\n",
    "        initDctBFS(root,0,None)\n",
    "        BFS(root,0,None)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        level_sum = defaultdict(int)\n",
    "        def bfs(root):\n",
    "            # 计算每一层的和\n",
    "            k = 0\n",
    "            q = deque()\n",
    "            q.append(root)\n",
    "            while len(q):\n",
    "                n = len(q)\n",
    "                for i in range(n):\n",
    "                    node = q.popleft()\n",
    "                    level_sum[k] += node.val\n",
    "                    if node.left:\n",
    "                        q.append(node.left)\n",
    "                    if node.right:\n",
    "                        q.append(node.right)\n",
    "                k += 1\n",
    "        bfs(root)\n",
    "        # return level_sum[0]\n",
    "        def dfs(node, s, k):\n",
    "            # 更新结点，当兄弟节点和为当前层的总和减去自己和兄弟节点的差\n",
    "            if node is None:\n",
    "                return\n",
    "            node.val = level_sum[k] - s\n",
    "            s = 0\n",
    "            if node.left:\n",
    "                s += node.left.val\n",
    "            if node.right:\n",
    "                s +=  node.right.val\n",
    "            dfs(node.left, s, k + 1)\n",
    "            dfs(node.right, s, k + 1)\n",
    "        dfs(root, root.val, 0)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        deep_sum_dict = defaultdict(int)\n",
    "        def a(node, deep):\n",
    "            deep_sum_dict[deep] += node.val\n",
    "            if node.left:\n",
    "                a(node.left, deep + 1)\n",
    "            if node.right:\n",
    "                a(node.right, deep + 1)\n",
    "        a(root, 1)\n",
    "        \n",
    "        def b(node, deep, c):\n",
    "            node.val = deep_sum_dict[deep] - c\n",
    "            son_sum = ((node.left.val if node.left else 0) + \n",
    "                       (node.right.val if node.right else 0))\n",
    "            if node.left:\n",
    "                b(node.left, deep + 1, son_sum)\n",
    "            if node.right:\n",
    "                b(node.right, deep + 1, son_sum)\n",
    "        b(root, 1, root.val)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        dic = {}\n",
    "        def dfs(root, i):\n",
    "            nonlocal dic\n",
    "            if root.left == None and root.right == None:\n",
    "                if i in dic:\n",
    "                    dic[i] = [int(dic[i][0]) + root.val]\n",
    "                else:\n",
    "                    dic[i] = [root.val]\n",
    "                return\n",
    "            i += 1\n",
    "            if root.left != None:\n",
    "                dfs(root.left, i)\n",
    "            if root.right != None:\n",
    "                dfs(root.right, i)\n",
    "            i -= 1\n",
    "            if i in dic:\n",
    "                dic[i] = [int(dic[i][0]) + root.val]\n",
    "            else:\n",
    "                dic[i] = [root.val]\n",
    "            return    \n",
    "        dfs(root,0)\n",
    "        \n",
    "        def dfs1(root,i):\n",
    "            nonlocal dic\n",
    "            if root.left == None and root.right == None:return\n",
    "            i += 1\n",
    "            if root.left != None:\n",
    "                dfs1(root.left,i)\n",
    "            if root.right != None:\n",
    "                dfs1(root.right,i)\n",
    "            i -= 1\n",
    "            if root.left == None:\n",
    "                root.right.val = int(dic[i][0])-root.right.val\n",
    "            elif root.right == None:\n",
    "                root.left.val = int(dic[i][0])-root.left.val\n",
    "            else:\n",
    "                root.left.val =root.right.val = int(dic[i][0])-root.left.val-root.right.val\n",
    "            return\n",
    "        dfs1(root,1)\n",
    "        return root\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.val = 0\n",
    "        dic = {}\n",
    "        def dfs(root, i):\n",
    "            nonlocal dic\n",
    "            if root.left == None and root.right == None:\n",
    "                if i in dic:\n",
    "                    dic[i] = [int(dic[i][0]) + root.val]\n",
    "                else:\n",
    "                    dic[i] = [root.val]\n",
    "                return\n",
    "            i += 1\n",
    "            if root.left != None:\n",
    "                dfs(root.left, i)\n",
    "            if root.right != None:\n",
    "                dfs(root.right, i)\n",
    "            i -= 1\n",
    "            if i in dic:\n",
    "                dic[i] = [int(dic[i][0]) + root.val]\n",
    "            else:\n",
    "                dic[i] = [root.val]\n",
    "            return    \n",
    "        dfs(root,0)\n",
    "        \n",
    "        def dfs1(root,i):\n",
    "            nonlocal dic\n",
    "            if root.left == None and root.right == None:return\n",
    "            i += 1\n",
    "            if root.left != None:\n",
    "                dfs1(root.left,i)\n",
    "            if root.right != None:\n",
    "                dfs1(root.right,i)\n",
    "            i -= 1\n",
    "            if root.left == None:\n",
    "                root.right.val = int(dic[i][0])-root.right.val\n",
    "            elif root.right == None:\n",
    "                root.left.val = int(dic[i][0])-root.left.val\n",
    "            else:\n",
    "                root.left.val =root.right.val = int(dic[i][0])-root.left.val-root.right.val\n",
    "            return\n",
    "        dfs1(root,1)\n",
    "        return root\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        level_sum = defaultdict(int)\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            level_sum[depth] += root.val\n",
    "            if root.left:\n",
    "                dfs(root.left, depth + 1)\n",
    "            if root.right:\n",
    "                dfs(root.right, depth + 1)\n",
    "\n",
    "        dfs(root, 0)\n",
    "\n",
    "        def dfs1(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            child_sum = 0\n",
    "            if root.left:\n",
    "                child_sum += root.left.val\n",
    "                dfs1(root.left, depth + 1)\n",
    "            if root.right:\n",
    "                child_sum += root.right.val\n",
    "                dfs1(root.right, depth + 1)\n",
    "            if root.left:\n",
    "                root.left.val = level_sum[depth + 1] - child_sum\n",
    "            if root.right:\n",
    "                root.right.val = level_sum[depth + 1] - child_sum\n",
    "        dfs1(root, 0)\n",
    "        root.val = 0\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
